#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    vector<string> goodsOrder(string goods)
    {
        int n = goods.size();
        _visited.resize(n, 0);
        std::sort(goods.begin(), goods.end());
        trace_back(goods, 0, n);
        return _res;
    }

private:
    void trace_back(const std::string& goods, int count, int n)
    {
        if (count == n) {
            _res.emplace_back(_s);
            return;
        }

        for (int i = 0; i < n; ++i)
        {
            if (_visited[i] == 1
                || (i != 0 && goods[i] == goods[i - 1] && _visited[i - 1] == 0))
            {
                continue;
            }
            _visited[i] = 1;
            _s += goods[i];
            trace_back(goods, count + 1, n);
            _s.pop_back();
            _visited[i] = 0;
        }
    }

    std::string _s;
    std::vector<std::string> _res;
    std::vector<int> _visited;
};